#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include<stdbool.h>
#include<iostream>
using namespace std;
typedef struct stack
{
	int* arr;
	int top;
	int capcity;
}ST;
bool StackEmpty(ST* p);
int Partion1(int* arr, int L, int R)
{
	int prev = L;
	int cur = L + 1;
	int first = arr[L];
	while (cur <= R)
	{
		if (arr[cur] < first && ++prev != cur)
		{
			swap(arr[cur], arr[prev]);
		}
		cur++;
	}
	swap(arr[L], arr[prev]);
	return prev;
}
void StackInit(ST* p)
{
	p->arr = (int*)malloc(sizeof(int) * 4);
	p->capcity = 4;
	p->top = 0;
}
void StackPush(ST* p, int x)
{
	if (p->top == p->capcity)
	{
		int* temp = (int*)realloc(p->arr, sizeof(int) * (p->capcity * 2));
		if (temp != NULL)
		{
			p->arr = temp;
			p->capcity *= 2;
		}
		p->arr[p->top] = x;
		p->top++;
	}
	else
	{
		p->arr[p->top] = x;
		p->top++;
	}
}
void StackPop(ST* p)
{
	assert(p);
	assert(p->top > 0);
	if (StackEmpty(p) == true)
	{
		printf("栈为空");
		return;
	}
	else
	{
		p->top--;
	}
}
void StackDestory(ST* p)
{
	free(p->arr);
	p->arr = NULL;
	p->top = 0;
	p->capcity = 0;
}
int StackTop(ST* p)
{
	assert(p);
	assert(p->top > 0);
	return p->arr[p->top - 1];
}
bool StackEmpty(ST* p)
{
	assert(p);
	return p->top == 0;
}
void StackShow(ST p)
{
	if (StackEmpty(&p) == 1)
	{
		printf("栈为空");
		return;
	}
	else
	{
		for (int i = p.top - 1; i >= 0; i--)
		{
			printf("%d ", p.arr[i]);
		}
	}
}
int StackSize(ST* p)
{
	assert(p);
	return p->top;
}
void InsertSort(int* arr, int length);
void swap(int* buf1, int* buf2)
{
	int temp = *buf1;
	*buf1 = *buf2;
	*buf2 = temp;
}
int Getmid(int* arr, int L, int R)
{
	int mid = L + (R - L) / 2;
	if (arr[L] > arr[mid])
	{
		if (arr[mid] > arr[R])
		{
			return mid;
		}
		else if (arr[L] > arr[R])
		{
			return R;
		}
		else
		{
			return L;
		}
	}
	else //arr[L] < arr[mid]
	{
		if (arr[L] > arr[R])
		{
			return L;
		}
		else if (arr[mid] > arr[R])
		{
			return R;
		}
		else
		{
			return mid;
		}
	}
}
void QuickSortCircle(int* arr, int L, int R) //非递归的快排
{
	ST stack;
	StackInit(&stack);
	StackPush(&stack, L);
	StackPush(&stack, R);

	while (!StackEmpty(&stack))
	{
		int right = StackTop(&stack);
		StackPop(&stack);
		int left = StackTop(&stack);
		StackPop(&stack);

		int mid = Partion1(arr, left, right);
		if (mid+1< R)
		{
			StackPush(&stack, mid + 1);
			StackPush(&stack, right);
		}
		if (left < mid -1)
		{
			StackPush(&stack, left);
			StackPush(&stack, mid-1);
		}
	}
	StackDestory(&stack);
}
void QuickSort(int* arr, int L, int R) //挖坑法
{
	if (L >= R)
	{
		return;
	}
	int left = L;
	int right = R;
	int first = arr[left];
	while (left < right)
	{
		while (left < right && arr[right] >= first)
		{
			right--;
		}

		if (left < right)
		{
			arr[left] = arr[right];
		}

		while (left < right && arr[left] <= first)
		{
			left++;
		}

		if (left < right)
		{
			arr[right] = arr[left];
		}

		if (left == right)
		{
			arr[left] = first;
		}
	}
	QuickSort(arr, L, left - 1);
	QuickSort(arr, left + 1, R);
}
void _QuickSort(int* arr, int L, int R) //前后指针法
{
	if (L >= R)
	{
		return;
	}
	int prev = L;
	int cur = L+1;
	int first = arr[L];
	while (cur <= R)
	{
		if (arr[cur] < first && ++prev != cur)
		{
			swap(arr[cur], arr[prev]);
		}
		cur++;
		/*	while (cur <= R && arr[cur] >= first)
		{
			cur++;
		}
		if (cur <= R)
		{
			prev++;
		}
		if (cur <= R &&  prev != cur)
		{
			swap(arr[prev], arr[cur]);

		}
		else
		{
			cur++;;
		}
		*/
	}
	swap(arr[L], arr[prev]);
	_QuickSort(arr, L, prev-1);
	_QuickSort(arr, prev+1, R);
}
void hoareQuickSort(int* arr, int L, int R) //hoare法
{
	if (L >= R)
	{
		return;
	}
	if ((R - L + 1) < 15) //小区间优化
	{
		InsertSort(arr + L, (R-L +1));
	}
	int mid = Getmid(arr, L, R); //三数取中
	swap(arr[L], arr[mid]);
	int left = L;
	int right = R;
	int key = arr[L];
	while (left < right)
	{
		while (left < right && arr[right] >= key)
		{
			right--;
		}
		while (left < right && arr[left] <= key)
		{
			left++;
		}
		if (left < right)
		{
			swap(arr[left], arr[right]);
		}
	}
	swap(&arr[left], &arr[L]);
	hoareQuickSort(arr, L, left - 1);
	hoareQuickSort(arr, left + 1, R);
}
void InsertSort(int* arr, int length)
{
	for (int i = 0; i < length-1; i++)
	{
		int end = i;
		int temp = arr[end + 1];
		while (end >= 0)
		{
			if (temp < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = temp;
	}
}
void ShellSort(int* arr, int length)
{
	int gap = length;
	while (gap > 1)
	{
		gap /= 2;
		for (int i=0; i < length - gap; i++)
		{
			int end = i;
			int temp = arr[end + gap];
			while (end >= 0)
			{
				if (temp < arr[end])
				{
					arr[end+gap] = arr[i];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end+gap] = temp;
		}
	}
}
void MergeSort(int* arr, int * temp,int L, int R)
{
	if (L >= R)
	{
		return;
	}
	int mid = (L + R) / 2;
	MergeSort(arr,temp,L, mid);
	MergeSort(arr,temp, mid + 1, R);
	int left = L,right = mid+1,k = L;
	while (left <= mid && right <= R)
	{
		if (arr[left] < arr[right])
		{
			temp[k++] = arr[left++];
		}
		else
		{
			temp[k++] = arr[right++];
		}
	}
	while (left <=mid)
	{
		temp[k++] = arr[left++];
	}
	while(right <= R)
	{
		temp[k++] = arr[right++];
	}
	for (int i = L; i <= R; i++)
	{
		arr[i] = temp[i];
	}
}
void Print(int* arr, int length)
{
	for (int i = 0; i < length; i++)
	{
		printf("%d ", arr[i]);
	}
}
void test01()
{
	int arr[] = { 10,9,8,7,6,5,4,3,2,1 };
	QuickSort(arr, 0, 9);
	Print(arr, sizeof(arr) / 4);
}
void test02()
{
	srand(time(0));
	int N = 10000;
	int* array = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++)
	{
		array[i] = rand();
	}
	ShellSort(array, N - 1);
	Print(array, N);
}
void test03()
{
	srand(time(0));
	int N = 10000;
	int* array = (int*)malloc(sizeof(int) * N);
	int* temp = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++)
	{
		array[i] = rand();
	}
	MergeSort(array,temp,0, N -1);
	Print(array, N);
}
void test04()
{
	srand(time(0));
	int N = 10000;
	int* array = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++)
	{
		array[i] = rand();
	}
	_QuickSort(array, 0, N-1);
	Print(array, N);
}
void test05()
{
	srand(time(0));
	int N = 10000;
	int* array = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++)
	{
		array[i] = rand();
	}
	hoareQuickSort(array, 0, N-1);
	Print(array, N);
}
void test06()
{
	srand(time(0));
	int N = 10000;
	int* array = (int*)malloc(sizeof(int) * N);
	int arr[] = { 4,1,3,7,9,2,6,5,10,8 };
	for (int i = 0; i < N; i++)
	{
		array[i] = rand();
	}
	//QuickSortCircle(arr, 0, 9);
	//Print(arr, 10);
	QuickSortCircle(array, 0, N - 1);
	Print(array, N);
}
void test07()
{
	srand(time(0));
	int N = 10000;
	int* array = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++)
	{
		array[i] = rand();
	}
	InsertSort(array,N);
	Print(array, N);
}
int main()
{
	test06();
}